﻿<!DOCTYPE html>
<html>
<head>
	<title>CAICAIBLOG</title>
	<meta charset="utf-8"/>
	<link rel="stylesheet" href="/font-awesome-4.7.0/css/font-awesome.min.css">
	<link rel="stylesheet" href="/bootstrap-3.3.7/css/bootstrap.min.css">
	<script src="/jquery-2.1.1/jquery.min.js"></script>
	<script src="/bootstrap-3.3.7/js/bootstrap.min.js"></script>
	<link rel="stylesheet" href="/main.css">
</head>
<body>
<link rel="stylesheet" href="/katex/katex.min.css" crossorigin="anonymous">
<script src="/katex/katex.min.js" crossorigin="anonymous"></script>
<script src="/katex/contrib/mathtex-script-type.min.js" defer></script>
<script defer src="/katex/contrib/auto-render.min.js"crossorigin="anonymous"
    onload="renderMathInElement(document.body);"></script>
<script>document.addEventListener("DOMContentLoaded", function() {renderMathInElement(document.body,{"delimiters":[{left: "$", right: "$", display: false}]});});</script>

<nav class="navbar navbar-default header card" role="navigation" style="width: 100%;">
	<div class="container-fluid"> 
	<div class="navbar-header">
		<button type="button" class="navbar-toggle" data-toggle="collapse"
				data-target="#example-navbar-collapse">
			<span class="icon-bar"></span>
			<span class="icon-bar"></span>
			<span class="icon-bar"></span>
		</button>
		<a class="navbar-brand" href="#">$\mathcal{CAICAIBLOG}$</a>
	</div>
	<div class="collapse navbar-collapse" id="example-navbar-collapse">
		<ul class="nav navbar-nav">
			<li><a href="/">首页</a></li>
			<li  class="active"><a href="#">文章</a></li>
			<li><a href="#">归档</a></li>
			<li><a href="#">标签</a></li>
		</ul>
	</div>
	</div>
</nav>
<div class="container">
	<div style="height: 60px;"></div>
	<div class="row" >
		<div class="col-md-8">
			<div class="panel panel-default card" style="padding: 10px;" id="main">
				<h1>CFXXXX</h1>
				<h2>题意</h2>
				<p>有一棵节点数为<script type="math/tex">n</script>的数，边有边权。现有宝藏等概率的在<script type="math/tex">2\to n</script>点，求发现宝藏最短的期望时间。
				<!--more--></p>
				<h2>题解</h2>
				<p><del>套路题</del></p>
				<p>做此题前建议先<script type="math/tex">\text{A}</script>了<a href="/problem/P3574">P3574</a></p>
				<p>考虑用<script type="math/tex">f_i</script>表示在<script type="math/tex">i</script>的子树中的最小期望时间，显然如果我们有排列好了遍历顺序，如果<script type="math/tex">w_i</script>为到<script type="math/tex">i</script>的边权，那么：
				<script type="math/tex; mode=display">f_i=\sum_{Son\in son_i}(\text{等待时间}+w_{Son}+f_{Son})\times P(\text{宝藏在}Son\text{中})</script>
				</p>
				<p>即<script type="math/tex">tim_i</script>为遍历完<script type="math/tex">i</script>的子树的时间</p>
				<p>那么再考虑如果<script type="math/tex">y</script>比<script type="math/tex">x</script>更优，则必然满足：
				<script type="math/tex; mode=display">(f_x+w_x)\times P(in\ x)+((tim_x+2w_x)+f_y+w_y)\times P(in\ y)>(f_y+w_y)\times P(in\ y)+((tim_y+2w_y)+f_x+w_x)\times P(in\ x)</script>
				记<script type="math/tex">tim_x+2\times w_x=g_x</script>，<script type="math/tex">sz_x</script>为子树的大小。</p>
				<p>经过简单的化简得到：</p>
				<p>
				<script type="math/tex; mode=display">\frac {g_y} {sz_y}<\frac {g_x}{sz_x}</script>
				</p>
				<p>按<script type="math/tex">\frac g{sz}</script>从小到大排序，再更新<script type="math/tex">f</script>即可</p>
				<h2>代码</h2>
				<br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br><br>
			</div>
			<div class="panel panel-default card" style="padding: 10px;height: 50px;font-size: 20px;">
				<a style="float: left;"><i class="fa fa-angle-double-left"></i></a>
				<a style="float: right;"><i class="fa fa-angle-double-right"></i></a>
			</div>
		</div>
		<div class="col-md-3">
				<div class="panel panel-default card">
				<div class="panel-heading">
					<h3 class="panel-title">
						<i class="fa fa-info"></i>&emsp;
						<strong>文章信息</strong>
					</h3>
				</div>
				</div>
				<div class="panel panel-default card">
				<div class="panel-heading">
					<h3 class="panel-title">
						<i class="fa fa-tag"></i>&emsp;
						<strong>标签</strong>
					</h3>
				</div>
				<div style="margin: 10px;">
				<a href="" class="tag"><span  style="background-color: deepskyblue;">asdd</span></a>
				
				</div>
				</div>
				<div class="panel panel-default card">
					<div class="panel-heading">
						<h3 class="panel-title">
							<i class="fa fa-user-circle-o"></i>&emsp;
							<strong>caijicjl</strong>
						</h3>
					</div>
					<div style="width: 60%;display: inline-block;padding-top: 10px;">
						<ul class="propertyLinks" style="list-style-type: none;">
							<li>
								<img style="vertical-align:middle;position:relative;top:-2px" src="/img/rating-16x16.png">
								Rating:&nbsp;
								<span style="font-weight:bold;color: #a0a">1958</span>
							</li>
							<li>
								<img style="vertical-align:middle;position:relative;top:-2px" src="/img/star_blue_16.png">
								Contribution:&nbsp;
								<span style="color:gray;font-weight:bold;">0</span>
							</li>
						</ul>
						<ul class="nav-links">
							<li><a href="/settings/general">Settings</a></li>
							<li><a href="/blog/dingdingsb">Blog</a></li>
							<li><a href="/teams">Teams</a></li>
							<li><a href="/submissions/dingdingsb">Submissions</a></li>
							<li><a href="/usertalk">Talks</a></li>
							<li><a href="/contests/with/dingdingsb">Contests</a></li>
						</ul>
					</div>
					<div style="display:inline-block;vertical-align: top;margin: 10px;text-align: center;">
						<div><img src="https://cdn.luogu.com.cn/upload/usericon/174304.png"/></div>
						<div><a href="https://www.luogu.com.cn/user/174304" style="font-weight:bold;color: #a0a;">caijicjl</a></div>
					</div>
				</div>
				
				<span id="kk"></span>
				<div  id="myScrollspy" class="card" style="width: 100%;"  data-spy="affix">
					<script src="/make_toc.js"></script>
					<i class="fa fa-spinner fa-spin"></i>
				</div>
		</div>
	</div>
 </div>
</body>
</html>